# 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

# 示例:

# 输入: n = 4, k = 2
# 输出:
# [
# [2,4],
# [3,4],
# [2,3],
# [1,2],
# [1,3],
# [1,4],
# ]

# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/combinations
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

"""
执行用时 : 44 ms , 在所有 Python3 提交中击败了 99.77% 的用户
内存消耗 : 14.8 MB , 在所有 Python3 提交中击败了 39.46% 的用户
2.89m
"""

from typing import List


class Solution:
    def __init__(self):
        self.res = []

    def recall(self, nums, k, c):
        if len(c) == k:
            self.res.append(c)
            return
        # 剪枝
        for i in range(len(nums) - (k - len(c)) + 1):
            self.recall(nums[i+1:], k, c + [nums[i]])

    def combine(self, n: int, k: int) -> List[List[int]]:
        if k == 0 or n == 0:
            return []

        nums = list(range(1, n+1))
        self.recall(nums, k, [])
        return self.res


if __name__ == "__main__":
    print(Solution().combine(4, 2))
